# 前序与中序构造数组


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 前序遍历的特点，第一个元素是根节点
# 中序遍历中找到根节点，分为左子树和右子树

class Solution:
    # 前提是无重复元素
    def buildTree(self, preorder:list[int], inorder:list[int]):
        if len(inorder) == 0:
            return None
        
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])

        root.left = self.buildTree(preorder[1: mid+1], inorder[: mid])
        root.right = self.buildTree(preorder[mid+1: ], inorder[mid+1: ])

        return root
    

if __name__ == "__main__":

    preorder = [3,9,20,15,7]
    inorder = [9,3,15,20,7]

    sol = Solution()
    res = sol.buildTree(preorder, inorder)



